# -*- coding:utf-8 -*-
import ctypes


class DynamicArray:
    """
    使用 ctypes 模块提供的原始数组实现 Dynamic Array 类（与原生Python的 List 类相似）
    """

    def __init__(self):
        """
        _length: 数组中存储的数据个数
        _capacity: 数组真实的容量
        _A: 低层次的数组
        """
        self._length = 0
        self._capacity = 1
        self._A = self._make_array(self._capacity)

    @staticmethod
    def _make_array(cap):
        return (cap * ctypes.py_object)()

    def __len__(self):
        return self._length

    def __getitem__(self, item):
        if not 0 <= item < self._length:
            raise IndexError("Invalid index!")
        return self._A[item]

    def __setitem__(self, key, value):
        self._A[key] = value

    def __str__(self):
        string = "["
        for i in range(self._length - 1):
            string += " " + str(self._A[i]) + ","
        string += f" {self._A[self._length - 1]} ]"
        return string

    def _resize(self):
        B = self._make_array(self._capacity * 2)
        for i in range(self._length):
            B[i] = self._A[i]
        self._A = B
        self._capacity *= 2

    def append(self, obj):
        if self._length == self._capacity:
            self._resize()
        self._A[self._length] = obj
        self._length += 1

    def insert(self, key, value):
        if self._length == self._capacity:
            self._resize()
        for i in range(self._length, key, -1):
            self._A[i] = self._A[i - 1]
        self._A[key] = value
        self._length += 1

    def remove(self, value):
        for i in range(self._length):
            if self._A[i] == value:
                for j in range(i, self._length - 1):
                    self._A[j] = self._A[j + 1]
                self._A[self._length - 1] = None
                self._length -= 1
                return
        raise ValueError("Value not found!")


if __name__ == "__main__":
    l = DynamicArray()
    l.append(1)
    l.append("abc")
    l.append(369)
    l.append(333)
    l[2] = 963
    l.insert(2, "def")
    print(l)
    l.remove(333)
    print(l)
